package com.atguigu.main.search;

import java.util.ArrayList;
import java.util.List;

/**
 * 二分查找法
 *
 * @Author 剧情再美终是戏
 * @Date 2019/12/23
 * @return
 * @Version 1.0
 **/
public class BinarySearch {

    /**
     * 将一个有序的集合进行二分查询(这个找到一个就返回了)
     *
     * @param array      一个有序的集合
     * @param leftIndex  集合的开始下标
     * @param rightIndex 集合的结束下标
     * @param val        需要查询的数据
     * @return int
     * @Author 剧情再美终是戏
     * @Date 2019/12/23
     * @Version 1.0
     **/
    public static int binarySearch(int[] array, int leftIndex, int rightIndex, int val) {

        // 参数过滤
        if (leftIndex < 0 || rightIndex > array.length || leftIndex > rightIndex) {
            return -1;
        }

        // 1 2 3 4 5 6 7 8 9 ---> 6
        // 计算二分查找的下标及获取到的值
        int midIndex = (leftIndex + rightIndex) / 2;
        int midVal = array[midIndex];

        if (midVal < val) {
            return binarySearch(array, midIndex, rightIndex, val);
        } else if (midVal > val) {
            return binarySearch(array, leftIndex, midIndex, val);
        } else {
            return midIndex;
        }
    }

    /**
     * 将一个有序的集合进行二分查询(这个找到一个就返回了)
     *
     * @param array      一个有序的集合
     * @param leftIndex  集合的开始下标
     * @param rightIndex 集合的结束下标
     * @param val        需要查询的数据
     * @return int
     * @Author 剧情再美终是戏
     * @Date 2019/12/23
     * @Version 1.0
     **/
    public static List<Integer> binarySearchs(int[] array, int leftIndex, int rightIndex, int val, List<Integer> result) {

        // 参数过滤
        if (leftIndex < 0 || rightIndex > array.length || leftIndex > rightIndex) {
            return result;
        }

        // 1 2 3 4 5 6 7 8 9 ---> 6
        // 计算二分查找的下标及获取到的值
        int midIndex = (leftIndex + rightIndex) / 2;
        int midVal = array[midIndex];

        if (midVal < val) {
            return binarySearchs(array, midIndex, rightIndex, val, result);
        } else if (midVal > val) {
            return binarySearchs(array, leftIndex, midIndex, val, result);
        } else {
            // 将找到的下标添加到集合中
            result.add(midIndex);

            // 向左查询相等的值
            binarySearchsLeft(array, midIndex, val, result);

            // 向右查询相等的值
            binarySearchsRight(array, midIndex, val, result);
        }
        return result;
    }

    public static void binarySearchsLeft(int[] array, int midIndex, int val, List<Integer> result) {
        for (int i = midIndex - 1; i >= 0; i--) {
            if (array[i] == val) {
                result.add(0, i);
            } else {
                break;
            }
        }
    }

    public static void binarySearchsRight(int[] array, int midIndex, int val, List<Integer> result) {
        for (int i = midIndex + 1; i < array.length; i++) {
            if (array[i] == val) {
                result.add(i);
            } else {
                break;
            }
        }
    }


    public static void main(String[] args) {
        int[] array = {1, 2, 3, 5, 5, 5, 5, 8, 9};
//        System.out.println(BinarySearch.binarySearch(array, 0, array.length - 1, 4));
        List<Integer> result = new ArrayList<Integer>();
        BinarySearch.binarySearchs(array, 0, array.length, 5, result);
        System.out.println(result);
    }
}
